#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n==1){
            return 1;
        }
        //计算第n个丑数
        int i = 0;
        int j = 0;
        int k = 0;
        vector<int> dp= {1};
        int sum = 1;
        int index = 1;
        while(index<n){
            int numi = dp[i]*2;
            int numj = dp[j]*3;
            int numk = dp[k]*5;
            int temp = min(min(numi,numj),numk);
            dp.push_back(temp);
            if(numi == temp){
                ++i;
            }
            if(temp == numj){
                ++j;
            }
            if(temp==numk){
                ++k;
            }
            ++index;
        }
        return dp[n-1];
    }
};

int main(){
    Solution S;
    cout<<S.nthUglyNumber(10)<<endl;
}
